<!DOCTYPE html>
<html lang="en-us">
  <head>
  <link href="http://gmpg.org/xfn/11" rel="profile">
  <meta http-equiv="X-UA-Compatible" content="IE=edge">
  <meta http-equiv="content-type" content="text/html; charset=utf-8">
  <!-- Enable responsiveness on mobile devices-->
  <meta name="viewport" content="width=device-width, initial-scale=1.0, maximum-scale=1">
  <title>
    
      Natural Language For Communication &middot; AIMA Exercises 
    
  </title>
  <!-- CSS -->
  <link rel="stylesheet" href="/aima-exercises/public/css/poole.css">
  <link rel="stylesheet" href="/aima-exercises/public/css/syntax.css">
  <link rel="stylesheet" href="/aima-exercises/public/css/lanyon.css">
  <link rel="stylesheet" href="/aima-exercises/public/css/style.css">
  <link rel="stylesheet" href="https://fonts.googleapis.com/css?family=PT+Serif:400,400italic,700%7CPT+Sans:400">
  <link rel="stylesheet" href="https://use.fontawesome.com/releases/v5.8.1/css/all.css" integrity="sha384-50oBUHEmvpQ+1lW4y57PTFmhCaXp0ML5d60M1M7uH2+nqUivzIebhndOJK28anvf" crossorigin="anonymous">

      <!-- Bootstrap CSS -->
      <link rel="stylesheet" href="https://stackpath.bootstrapcdn.com/bootstrap/4.3.1/css/bootstrap.min.css" integrity="sha384-ggOyR0iXCbMQv3Xipma34MD+dH/1fQ784/j6cY/iJTQUOhcWr7x9JvoRxT2MZw1T" crossorigin="anonymous">

  <!-- Icons -->
  <link rel="apple-touch-icon-precomposed" sizes="144x144" href="/aima-exercises/public/apple-touch-icon-precomposed.png">
  <link rel="shortcut icon" href="/aima-exercises/public/aima_logo.ico">

  <!-- RSS -->
  <link rel="alternate" type="application/rss+xml" title="RSS" href="/atom.xml">
</head>

  <body>
    <!-- Target for toggling the sidebar `.sidebar-checkbox` is for regular
     styles, `#sidebar-checkbox` for behavior. -->
<input type="checkbox" class="sidebar-checkbox" id="sidebar-checkbox">

<!-- Toggleable sidebar -->
<div class="sidebar" id="sidebar">
  <div class="sidebar-item">
    <p>Artificial Intelligence : A Modern Approach</p>
  </div>

  <nav class="sidebar-nav">
    <a class="sidebar-nav-item" href="/aima-exercises/">Home</a>
    <span class="sidebar-nav-item">Part - I Artificial Intelligence</span>
  <a class="sidebar-nav-item" href="/aima-exercises/intro-exercises/">Chapter 1 - Introduction</a>
  <a class="sidebar-nav-item" href="/aima-exercises/agents-exercises/">Chapter 2 - Intelligent Agents</a>
  <span class="sidebar-nav-item">Part - II Problem Solving</span>
  <a class="sidebar-nav-item" href="/aima-exercises/search-exercises/">Chapter 3 - Solving Problems By Searching</a>
  <a class="sidebar-nav-item" href="/aima-exercises/advanced-search-exercises">Chapter 4 - Beyond Classical Search</a>
  <a class="sidebar-nav-item" href="/aima-exercises/game-playing-exercises">Chapter 5 - Adversarial Search</a>
  <a class="sidebar-nav-item" href="/aima-exercises/csp-exercises">Chapter 6 - Constraint Satisfaction Problems</a>
  <span class="sidebar-nav-item">Part - III Knowledge, Reasoning and Planning</span>
  <a class="sidebar-nav-item" href="/aima-exercises/knowledge-logic-exercises">Chapter 7 - Logical Agents</a>
  <a class="sidebar-nav-item" href="/aima-exercises/fol-exercises">Chapter 8 - First Order Logic</a>
  <a class="sidebar-nav-item" href="/aima-exercises/logical-inference-exercises">Chapter 9 - Inference in First Order Logic</a>
  <a class="sidebar-nav-item" href="/aima-exercises/planning-exercises">Chapter 10 - Classical Planning</a>
  <a class="sidebar-nav-item" href="/aima-exercises/advanced-planning-exercises">Chapter 11 - Planning and Acting in Real Life</a>
  <a class="sidebar-nav-item" href="/aima-exercises/kr-exercises">Chapter 12 - Knowledge Representation</a>
  <span class="sidebar-nav-item">Part - IV Uncertaing Knowledge and Reasoning</span>
  <a class="sidebar-nav-item" href="/aima-exercises/probability-exercises">Chapter 13 - Quantifying Uncertainty</a>
  <a class="sidebar-nav-item" href="/aima-exercises/bayes-nets-exercises">Chapter 14 - Probabilistic Reasoning</a>
  <a class="sidebar-nav-item" href="/aima-exercises/dbn-exercises">Chapter 15 - Probabilistic Reasoning Over Time</a>
  <a class="sidebar-nav-item" href="/aima-exercises/decision-theory-exercises">Chapter 16 - Making-Simple Decisions</a>
  <a class="sidebar-nav-item" href="/aima-exercises/complex-decisions-exercises">Chapter 17 - Making Complex Decisions</a>
  <span class="sidebar-nav-item">Part - V Lerning</span>
  <a class="sidebar-nav-item" href="/aima-exercises/concept-learning-exercises">Chapter 18 - Learning From Examples</a>
  <a class="sidebar-nav-item" href="/aima-exercises/ilp-exercises">Chapter 19 - Knowledge In Learning</a>
  <a class="sidebar-nav-item" href="/aima-exercises/bayesian-learning-exercises">Chapter 20 - Learning Probabilistic Models</a>
  <a class="sidebar-nav-item" href="/aima-exercises/reinforcement-learning-exercises">Chapter 21 - Reinforcement Learning</a>
  <span class="sidebar-nav-item">Part - VI Communicating, Perceiving and Acting</span>
  <a class="sidebar-nav-item" href="/aima-exercises/nlp-communicating-exercises">Chapter 22 - Natural Language Processing</a>
  <a class="sidebar-nav-item" href="/aima-exercises/nlp-english-exercises">Chapter 23 - Natural Language For Communication</a>
  <a class="sidebar-nav-item" href="/aima-exercises/perception-exercises">Chapter 24 - Perception</a>
  <a class="sidebar-nav-item" href="/aima-exercises/robotics-exercises">Chapter 25 - Robotics</a>
  <span class="sidebar-nav-item">Part - VII Conclusions</span>
  <a class="sidebar-nav-item" href="/aima-exercises/philosophy-exercises">Chapter 26 - Philosophical Foundations</a>
  <a class="sidebar-nav-item" href="/aima-exercises/#/">Chapter 27 - AI The Present And Future</a>
    <span class="sidebar-nav-item">Currently v1.0.0</span>
  </nav>

  <div class="sidebar-item">
    <p>
      &copy; 2019. All rights reserved.
    </p>
  </div>
</div>

    <div class="wrap">
      <div class="masthead">
        <div class="container">
          <h3 class="masthead-title">
            <a href="/aima-exercises/" title="Home">Artificial Intelligence</a>
            <small>AIMA Exercises </small>
          </h3>
          <br>
          <center>
            <form class="form-inline active-pink-3 active-pink-4" action="/aima-exercises/search" id="site_search" autocomplete="off" method="GET">
              <i class="fas fa-search" aria-hidden="true"></i>
            <input class="form-control form-control-sm ml-3 w-75" type="text" placeholder="Search within AIMA Exercises" aria-label="Search" name="query">
            <input type="submit" value="Go!" class="search-btn">
            </form>
            <br>
            </center>
            



<ul class="breadcrumbb" id="bbreadcrumb">

  <label for="toggletoc" class="toc-icon">
    <span></span>
    <span></span>
    <span></span>
  </label>

   
   
    <li><a class="breadcrumb-text" href="/aima-exercises/"><i class="fa fa-home"></i></a>  </li>
   


</ul>

      </div>
    </div>
      <div class="container content">
        <article class="post">

  <div class="entry">
    <script type="text/x-mathjax-config">
  MathJax.Hub.Config({
    TeX: {
      equationNumbers: {
        autoNumber: "AMS"
      }
    },
    tex2jax: {
      inlineMath: [ ['$','$'] ],
      displayMath: [ ['$$','$$'] ],
      processEscapes: true,
    },
    "HTML-CSS": { 
      preferredFont: "TeX", 
      availableFonts: ["STIX","TeX"], 
      styles: {".MathJax": {}} 
    }
  });
</script>

<script type="text/javascript" src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.0/MathJax.js?config=TeX-AMS-MML_HTMLorMML">
</script>

<h1 id="23-natural-language-for-communication">23. Natural Language for Communication</h1>

<div class="card">
<div class="card-header p-2">
<a href="ex_1/" class="p-2">Exercise 1 (washing-clothes-exercise) </a>
<button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch23ex1');" href="#"><i id="ch23ex1" class="fas fa-bookmark" style="color:white"></i></button>
<button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex23.1);" href="#"><i id="ch23ex1" class="fas fa-thumbs-up" style="color:white"></i></button>
</div>
<div class="card-body">
<p class="card-text">

Read the following text once for
understanding, and remember as much of it as you can. There will be a
test later.<br />

&gt; The procedure is actually quite simple. First you arrange things into
different groups. Of course, one pile may be sufficient depending on how
much there is to do. If you have to go somewhere else due to lack of
facilities that is the next step, otherwise you are pretty well set. It
is important not to overdo things. That is, it is better to do too few
things at once than too many. In the short run this may not seem
important but complications can easily arise. A mistake is expensive as
well. At first the whole procedure will seem complicated. Soon, however,
it will become just another facet of life. It is difficult to foresee
any end to the necessity for this task in the immediate future, but then
one can never tell. After the procedure is completed one arranges the
material into different groups again. Then they can be put into their
appropriate places. Eventually they will be used once more and the whole
cycle will have to be repeated. However, this is part of life.
</p>
</div>
</div>
<p><br /></p>
<div class="card">
<div class="card-header p-2">
<a href="ex_2/" class="p-2">Exercise 2 </a>
<button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch23ex2');" href="#"><i id="ch23ex2" class="fas fa-bookmark" style="color:white"></i></button>
<button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex23.2);" href="#"><i id="ch23ex2" class="fas fa-thumbs-up" style="color:white"></i></button>
</div>
<div class="card-body">
<p class="card-text">

An <i>HMM grammar</i> is essentially a standard HMM whose state
variable is $N$ (nonterminal, with values such as $Det$, $Adjective$,
$Noun$ and so on) and whose evidence variable is $W$ (word, with values
such as $is$, $duck$, and so on). The HMM model includes a prior
${\textbf{P}}(N_0)$, a transition model
${\textbf{P}}(N_{t+1}|N_t)$, and a sensor model
${\textbf{P}}(W_t|N_t)$. Show that every HMM grammar can be
written as a PCFG. [Hint: start by thinking about how the HMM prior can
be represented by PCFG rules for the sentence symbol. You may find it
helpful to illustrate for the particular HMM with values $A$, $B$ for
$N$ and values $x$, $y$ for $W$.]
</p>
</div>
</div>
<p><br /></p>
<div class="card">
<div class="card-header p-2">
<a href="ex_3/" class="p-2">Exercise 3 </a>
<button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch23ex3');" href="#"><i id="ch23ex3" class="fas fa-bookmark" style="color:white"></i></button>
<button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex23.3);" href="#"><i id="ch23ex3" class="fas fa-thumbs-up" style="color:white"></i></button>
</div>
<div class="card-body">
<p class="card-text">

Consider the following PCFG for simple verb phrases:<br />

&gt; 0.1: VP $\rightarrow$ Verb<br />

&gt; 0.2: VP $\rightarrow$ Copula Adjective<br />

&gt; 0.5: VP $\rightarrow$ Verb the Noun<br />

&gt; 0.2: VP $\rightarrow$ VP Adverb<br />

&gt; 0.5: Verb $\rightarrow$ is<br />

&gt; 0.5: Verb $\rightarrow$ shoots<br />

&gt; 0.8: Copula $\rightarrow$ is<br />

&gt; 0.2: Copula $\rightarrow$ seems<br />

&gt; 0.5: Adjective $\rightarrow$ <b>unwell</b><br />

&gt; 0.5: Adjective $\rightarrow$ <b>well</b><br />

&gt; 0.5: Adverb $\rightarrow$ <b>well</b><br />

&gt; 0.5: Adverb $\rightarrow$ <b>badly</b><br />

&gt; 0.6: Noun $\rightarrow$ <b>duck</b><br />

&gt; 0.4: Noun $\rightarrow$ <b>well</b><br />

1.  Which of the following have a nonzero probability as a VP? (i)
    shoots the duck well well well(ii) seems the well well(iii) shoots
    the unwell well badly<br />

2.  What is the probability of generating “is well well”?<br />

3.  What types of ambiguity are exhibited by the phrase in (b)?<br />

4.  Given any PCFG, is it possible to calculate the probability that the
    PCFG generates a string of exactly 10 words?<br />
</p>
</div>
</div>
<p><br /></p>
<div class="card">
<div class="card-header p-2">
<a href="ex_4/" class="p-2">Exercise 4 </a>
<button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch23ex4');" href="#"><i id="ch23ex4" class="fas fa-bookmark" style="color:white"></i></button>
<button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex23.4);" href="#"><i id="ch23ex4" class="fas fa-thumbs-up" style="color:white"></i></button>
</div>
<div class="card-body">
<p class="card-text">

Consider the following simple PCFG for noun phrases:<br />

&gt; 0.6: NP $\rightarrow$ Det\ AdjString\ Noun<br />

&gt; 0.4: NP $\rightarrow$ Det\ NounNounCompound<br />

&gt; 0.5: AdjString $\rightarrow$ Adj\ AdjString<br />

&gt; 0.5: AdjString $\rightarrow$ $\Lambda$<br />

&gt; 1.0: NounNounCompound $\rightarrow$ Noun<br />

&gt; 0.8: Det $\rightarrow$ <b>the</b><br />

&gt; 0.2: Det $\rightarrow$ <b>a</b><br />

&gt; 0.5: Adj $\rightarrow$ <b>small</b><br />

&gt; 0.5: Adj $\rightarrow$ <b>green</b><br />

&gt; 0.6: Noun $\rightarrow$ <b>village</b><br />

&gt; 0.4: Noun $\rightarrow$ <b>green</b><br />

where $\Lambda$ denotes the empty string.<br />

1.  What is the longest NP that can be generated by this grammar? (i)
    three words(ii) four words(iii) infinitely many words<br />

2.  Which of the following have a nonzero probability of being generated
    as complete NPs? (i) a small green village(ii) a green
    green green(iii) a small village green<br />

3.  What is the probability of generating “the green green”?<br />

4.  What types of ambiguity are exhibited by the phrase in (c)?<br />

5.  Given any PCFG and any finite word sequence, is it possible to
    calculate the probability that the sequence was generated by the
    PCFG?<br />
</p>
</div>
</div>
<p><br /></p>
<div class="card">
<div class="card-header p-2">
<a href="ex_5/" class="p-2">Exercise 5 </a>
<button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch23ex5');" href="#"><i id="ch23ex5" class="fas fa-bookmark" style="color:white"></i></button>
<button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex23.5);" href="#"><i id="ch23ex5" class="fas fa-thumbs-up" style="color:white"></i></button>
</div>
<div class="card-body">
<p class="card-text">

Outline the major differences between Java (or any other computer
language with which you are familiar) and English, commenting on the
“understanding” problem in each case. Think about such things as
grammar, syntax, semantics, pragmatics, compositionality,
context-dependence, lexical ambiguity, syntactic ambiguity, reference
finding (including pronouns), background knowledge, and what it means to
“understand” in the first place.
</p>
</div>
</div>
<p><br /></p>
<div class="card">
<div class="card-header p-2">
<a href="ex_6/" class="p-2">Exercise 6 </a>
<button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch23ex6');" href="#"><i id="ch23ex6" class="fas fa-bookmark" style="color:white"></i></button>
<button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex23.6);" href="#"><i id="ch23ex6" class="fas fa-thumbs-up" style="color:white"></i></button>
</div>
<div class="card-body">
<p class="card-text">

This exercise concerns grammars for very simple languages.<br />

1.  Write a context-free grammar for the language $a^n b^n$.<br />

2.  Write a context-free grammar for the palindrome language: the set of
    all strings whose second half is the reverse of the first half.<br />

3.  Write a context-sensitive grammar for the duplicate language: the
    set of all strings whose second half is the same as the first half.<br />
</p>
</div>
</div>
<p><br /></p>
<div class="card">
<div class="card-header p-2">
<a href="ex_7/" class="p-2">Exercise 7 </a>
<button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch23ex7');" href="#"><i id="ch23ex7" class="fas fa-bookmark" style="color:white"></i></button>
<button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex23.7);" href="#"><i id="ch23ex7" class="fas fa-thumbs-up" style="color:white"></i></button>
</div>
<div class="card-body">
<p class="card-text">

Consider the sentence “Someone walked slowly to the supermarket” and a
lexicon consisting of the following words:<br />

$Pronoun \rightarrow \textbf{someone} \quad Verb \rightarrow \textbf{walked}$<br />

$Adv \rightarrow \textbf{slowly} \quad Prep \rightarrow \textbf{to}$<br />

$Article \rightarrow \textbf{the} \quad Noun \rightarrow \textbf{supermarket}$<br />

Which of the following three grammars, combined with the lexicon,
generates the given sentence? Show the corresponding parse tree(s).<br />

$$
\quad\quad\quad\quad (A):\quad\quad\quad\quad  \quad\quad\quad\quad(B):\quad\quad\quad\quad  \quad\quad\quad\quad(C):\\
\quad\quad\quad\quad S \rightarrow NP \space VP \quad\quad\quad\quad \quad\quad\quad\quad S\rightarrow NP\space VP \quad\quad\quad\quad S\rightarrow NP\space VP\\
\quad\quad\quad\quad NP\rightarrow Pronoun \quad\quad\quad\quad  NP\rightarrow Pronoun \quad\quad\quad\quad  NP\rightarrow Pronoun\\
\quad\quad\quad\quad NP\rightarrow Article\space Noun \quad\quad\quad\quad  NP\rightarrow Noun \quad\quad\quad\quad  NP\rightarrow Article\space NP\\
\quad\quad\quad\quad VP\rightarrow VP\space PP \quad\quad\quad\quad NP\rightarrow Article\space NP \quad\quad\quad\quad  VP\rightarrow Verb\space Adv\\
\quad\quad\quad\quad  VP\rightarrow VP\space Adv\space Adv \quad\quad\quad\quad  VP\rightarrow Verb\space Vmod \quad\quad\quad\quad  Adv\rightarrow Adv\space Adv\\
\quad\quad\quad\quad  VP\rightarrow Verb \quad\quad\quad\quad  Vmod\rightarrow Adv\space Vmod \quad\quad\quad\quad   Adv\rightarrow PP\\
\quad\quad\quad\quad PP\rightarrow Prep\space NP \quad\quad\quad\quad Vmod\rightarrow Adv \quad\quad\quad\quad PP\rightarrow Prep\space NP\\
\quad\quad\quad\quad NP\rightarrow Noun \quad\quad\quad\quad Adv\rightarrow PP \quad\quad\quad\quad NP\rightarrow Noun\\
\quad\quad\quad\quad\quad \quad\quad\quad\quad PP\rightarrow Prep\space NP \quad\quad\quad\quad \quad\quad\quad\quad

$$

For each of the preceding three grammars, write down three sentences of
English and three sentences of non-English generated by the grammar.
Each sentence should be significantly different, should be at least six
words long, and should include some new lexical entries (which you
should define). Suggest ways to improve each grammar to avoid generating
the non-English sentences.
</p>
</div>
</div>
<p><br /></p>
<div class="card">
<div class="card-header p-2">
<a href="ex_8/" class="p-2">Exercise 8 </a>
<button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch23ex8');" href="#"><i id="ch23ex8" class="fas fa-bookmark" style="color:white"></i></button>
<button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex23.8);" href="#"><i id="ch23ex8" class="fas fa-thumbs-up" style="color:white"></i></button>
</div>
<div class="card-body">
<p class="card-text">

Collect some examples of time expressions, such as “two o’clock,”
“midnight,” and “12:46.” Also think up some examples that are
ungrammatical, such as “thirteen o’clock” or “half past two fifteen.”
Write a grammar for the time language.
</p>
</div>
</div>
<p><br /></p>
<div class="card">
<div class="card-header p-2">
<a href="ex_9/" class="p-2">Exercise 9 </a>
<button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch23ex9');" href="#"><i id="ch23ex9" class="fas fa-bookmark" style="color:white"></i></button>
<button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex23.9);" href="#"><i id="ch23ex9" class="fas fa-thumbs-up" style="color:white"></i></button>
</div>
<div class="card-body">
<p class="card-text">

Some linguists have argued as follows:<br />
<br />
 Children learning a language hear only <i>positive
 examples</i> of the language and no <i>negative
 examples</i>. Therefore, the hypothesis that “every possible
 sentence is in the language” is consistent with all the observed
 examples. Moreover, this is the simplest consistent hypothesis.
 Furthermore, all grammars for languages that are supersets of the true
 language are also consistent with the observed data. Yet children do
 induce (more or less) the right grammar. It follows that they begin
 with very strong innate grammatical constraints that rule out all of
 these more general hypotheses <i>a priori</i>.<br />

Comment on the weak point(s) in this argument from a statistical
learning viewpoint.
</p>
</div>
</div>
<p><br /></p>
<div class="card">
<div class="card-header p-2">
<a href="ex_10/" class="p-2">Exercise 10 (chomsky-form-exercise) </a>
<button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch23ex10');" href="#"><i id="ch23ex10" class="fas fa-bookmark" style="color:white"></i></button>
<button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex23.10);" href="#"><i id="ch23ex10" class="fas fa-thumbs-up" style="color:white"></i></button>
</div>
<div class="card-body">
<p class="card-text">

In this exercise you will transform $\large \varepsilon_0$  into
Chomsky Normal Form (CNF). There are five steps: (a) Add a new start
symbol, (b) Eliminate $\epsilon$ rules, (c) Eliminate multiple words on
right-hand sides, (d) Eliminate rules of the form
(${\it X} \rightarrow$${\it Y}$),
(e) Convert long right-hand sides into binary rules.<br />

1.  The start symbol, $S$, can occur only on the left-hand side in CNF.
    Replace ${\it S}$ everywhere by a new symbol
    ${\it S'}$ and add a rule of the form
    ${\it S}$
    $\rightarrow$${\it S'}$.<br />

2.  The empty string, $\epsilon$ cannot appear on the right-hand side
    in CNF. $\large \varepsilon_0$ does not have any rules with $\epsilon$, so this is not
    an issue.<br />

3.  A word can appear on the right-hand side in a rule only of the form
    (${\it X}$
    $\rightarrow$<i>word</i>).
    Replace each rule of the form (${\it X}$
    $\rightarrow$…<i>word</i> …)
    with (${\it X}$
    $\rightarrow$…${\it W'}$ …)
    and (${\it W'}$
    $\rightarrow$<i>word</i>),
    using a new symbol ${\it W'}$.<br />

4.  A rule (${\it X}$
    $\rightarrow$${\it Y}$)
    is not allowed in CNF; it must be (${\it X}$
    $\rightarrow$${\it Y}$
    ${\it Z}$) or (${\it X}$
    $\rightarrow$<i>word</i>).
    Replace each rule of the form (${\it X}$
    $\rightarrow$${\it Y}$)
    with a set of rules of the form (${\it X}$
    $\rightarrow$…), one
    for each rule (${\it Y}$
    $\rightarrow$…),
    where (…) indicates one or more symbols.<br />

5.  Replace each rule of the form (${\it X}$
    $\rightarrow$${\it Y}$
    ${\it Z}$ …) with two rules, (${\it X}$
    $\rightarrow$${\it Y}$
    ${\it Z'}$) and (${\it Z'}$
    $\rightarrow$${\it Z}$
    …), where ${\it Z'}$ is a new symbol.<br />

Show each step of the process and the final set of rules.<br />
</p>
</div>
</div>
<p><br /></p>
<div class="card">
<div class="card-header p-2">
<a href="ex_11/" class="p-2">Exercise 11 </a>
<button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch23ex11');" href="#"><i id="ch23ex11" class="fas fa-bookmark" style="color:white"></i></button>
<button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex23.11);" href="#"><i id="ch23ex11" class="fas fa-thumbs-up" style="color:white"></i></button>
</div>
<div class="card-body">
<p class="card-text">

Consider the following toy grammar:<br />

&gt; $S \rightarrow NP\space VP$<br />

&gt; $NP \rightarrow Noun$<br />

&gt; $NP \rightarrow NP\space and\space NP$<br />

&gt; $NP \rightarrow NP\space PP$<br />

&gt; $VP \rightarrow Verb$<br />

&gt; $VP \rightarrow VP\space and \space VP$<br />

&gt; $VP \rightarrow VP\space PP$<br />

&gt; $PP \rightarrow Prep\space NP$<br />

&gt; $Noun \rightarrow Sally\space; pools\space; streams\space; swims$<br />

&gt; $Prep \rightarrow in$<br />

&gt; $Verb \rightarrow pools\space; streams\space; swims$<br />

1.  Show all the parse trees in this grammar for the sentence “Sally
    swims in streams and pools.”<br />

2.  Show all the table entries that would be made by
    a (non-probabalistic) CYK parser on this sentence.<br />
</p>
</div>
</div>
<p><br /></p>
<div class="card">
<div class="card-header p-2">
<a href="ex_12/" class="p-2">Exercise 12(exercise-subj-verb-agree) </a>
<button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch23ex12');" href="#"><i id="ch23ex12" class="fas fa-bookmark" style="color:white"></i></button>
<button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex23.12);" href="#"><i id="ch23ex12" class="fas fa-thumbs-up" style="color:white"></i></button>
</div>
<div class="card-body">
<p class="card-text">

Using DCG notation, write a grammar for a
language that is just like $\large \varepsilon_1$, except that it enforces agreement between
the subject and verb of a sentence and thus does not generate
ungrammatical sentences such as “I smells the wumpus.”
</p>
</div>
</div>
<p><br /></p>
<div class="card">
<div class="card-header p-2">
<a href="ex_13/" class="p-2">Exercise 13 </a>
<button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch23ex13');" href="#"><i id="ch23ex13" class="fas fa-bookmark" style="color:white"></i></button>
<button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex23.13);" href="#"><i id="ch23ex13" class="fas fa-thumbs-up" style="color:white"></i></button>
</div>
<div class="card-body">
<p class="card-text">

Consider the following PCFG:<br />

&gt; $S \rightarrow NP \space VP[1.0] $<br />

&gt; $NP \rightarrow \textit{Noun}[0.6] \space|\space \textit{Pronoun}[0.4] $<br />

&gt; $VP \rightarrow \textit{Verb} \space NP[0.8] \space|\space \textit{Modal}\space \textit{Verb}[0.2]$<br />

&gt; $\textit{Noun} \rightarrow \textbf{can}[0.1] \space|\space \textbf{fish}[0.3] \space|\space ...$<br />

&gt; $\textit{Pronoun} \rightarrow \textbf{I}[0.4] \space|\space ...$<br />

&gt; $\textit{Verb} \rightarrow \textbf{can}[0.01] \space|\space \textbf{fish}[0.1] \space|\space ...$<br />

&gt; $\textit{Modal} \rightarrow \textbf{can}[0.3] \space|\space ...$<br />

The sentence “I can fish” has two parse trees with this grammar. Show
the two trees, their prior probabilities, and their conditional
probabilities, given the sentence.
</p>
</div>
</div>
<p><br /></p>
<div class="card">
<div class="card-header p-2">
<a href="ex_14/" class="p-2">Exercise 14 </a>
<button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch23ex14');" href="#"><i id="ch23ex14" class="fas fa-bookmark" style="color:white"></i></button>
<button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex23.14);" href="#"><i id="ch23ex14" class="fas fa-thumbs-up" style="color:white"></i></button>
</div>
<div class="card-body">
<p class="card-text">

An augmented context-free grammar can represent languages that a regular
context-free grammar cannot. Show an augmented context-free grammar for
the language $a^nb^nc^n$. The allowable values for augmentation
variables are 1 and $SUCCESSOR(n)$, where $n$ is a value. The rule for a sentence
in this language is<br />
$$S(n) \rightarrow A(n) B(n) C(n) \ .$$
Show the rule(s) for each of ${\it A}$,
${\it B}$, and ${\it C}$.
</p>
</div>
</div>
<p><br /></p>
<div class="card">
<div class="card-header p-2">
<a href="ex_15/" class="p-2">Exercise 15 </a>
<button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch23ex15');" href="#"><i id="ch23ex15" class="fas fa-bookmark" style="color:white"></i></button>
<button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex23.15);" href="#"><i id="ch23ex15" class="fas fa-thumbs-up" style="color:white"></i></button>
</div>
<div class="card-body">
<p class="card-text">

Augment the $\large \varepsilon_1$ grammar so that it handles article–noun agreement. That is,
make sure that “agents” and “an agent” are ${\it NP}$s, but
“agent” and “an agents” are not.
</p>
</div>
</div>
<p><br /></p>
<div class="card">
<div class="card-header p-2">
<a href="ex_16/" class="p-2">Exercise 16 </a>
<button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch23ex16');" href="#"><i id="ch23ex16" class="fas fa-bookmark" style="color:white"></i></button>
<button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex23.16);" href="#"><i id="ch23ex16" class="fas fa-thumbs-up" style="color:white"></i></button>
</div>
<div class="card-body">
<p class="card-text">

Consider the following sentence (from <i>The New York Times,</i>
July 28, 2008):<br />

&gt; Banks struggling to recover from multibillion-dollar loans on real
&gt; estate are curtailing loans to American businesses, depriving even
&gt; healthy companies of money for expansion and hiring.

1.  Which of the words in this sentence are lexically ambiguous?<br />

2.  Find two cases of syntactic ambiguity in this sentence (there are
    more than two.)<br />

3.  Give an instance of metaphor in this sentence.<br />

4.  Can you find semantic ambiguity?
<br />
</p>
</div>
</div>
<p><br /></p>
<div class="card">
<div class="card-header p-2">
<a href="ex_17/" class="p-2">Exercise 17 (washing-clothes2-exercise) </a>
<button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch23ex17');" href="#"><i id="ch23ex17" class="fas fa-bookmark" style="color:white"></i></button>
<button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex23.17);" href="#"><i id="ch23ex17" class="fas fa-thumbs-up" style="color:white"></i></button>
</div>
<div class="card-body">
<p class="card-text">

Without looking back at
Exercise <a class="exerciseRef" href="/aima-exercises/nlp-english-exercises/ex_1/">washing-clothes-exercise</a>, answer the following
questions:<br />

1.  What are the four steps that are mentioned?<br />

2.  What step is left out?<br />

3.  What is “the material” that is mentioned in the text?<br />

4.  What kind of mistake would be expensive?<br />

5.  Is it better to do too few things or too many? Why?<br />
</p>
</div>
</div>
<p><br /></p>
<div class="card">
<div class="card-header p-2">
<a href="ex_18/" class="p-2">Exercise 18 </a>
<button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch23ex18');" href="#"><i id="ch23ex18" class="fas fa-bookmark" style="color:white"></i></button>
<button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex23.18);" href="#"><i id="ch23ex18" class="fas fa-thumbs-up" style="color:white"></i></button>
</div>
<div class="card-body">
<p class="card-text">

Select five sentences and submit them to an online translation service.
Translate them from English to another language and back to English.
Rate the resulting sentences for grammaticality and preservation of
meaning. Repeat the process; does the second round of iteration give
worse results or the same results? Does the choice of intermediate
language make a difference to the quality of the results? If you know a
foreign language, look at the translation of one paragraph into that
language. Count and describe the errors made, and conjecture why these
errors were made.
</p>
</div>
</div>
<p><br /></p>
<div class="card">
<div class="card-header p-2">
<a href="ex_19/" class="p-2">Exercise 19 </a>
<button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch23ex19');" href="#"><i id="ch23ex19" class="fas fa-bookmark" style="color:white"></i></button>
<button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex23.19);" href="#"><i id="ch23ex19" class="fas fa-thumbs-up" style="color:white"></i></button>
</div>
<div class="card-body">
<p class="card-text">

The $D_i$ values for the sentence in
Figure <a class="insideBookFigRef" target="_blank" href="https://aimacode.github.io/aima-exercises/figures/mt-alignment-figure.png">mt-alignment-figure</a> sum to 0. Will that be true
of every translation pair? Prove it or give a counterexample.
</p>
</div>
</div>
<p><br /></p>
<div class="card">
<div class="card-header p-2">
<a href="ex_20/" class="p-2">Exercise 20 </a>
<button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch23ex20');" href="#"><i id="ch23ex20" class="fas fa-bookmark" style="color:white"></i></button>
<button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex23.20);" href="#"><i id="ch23ex20" class="fas fa-thumbs-up" style="color:white"></i></button>
</div>
<div class="card-body">
<p class="card-text">

(Adapted from [<a class="paperRef" title="" href="">Knight:1999</a>].) Our translation model assumes that, after the phrase
translation model selects phrases and the distortion model permutes
them, the language model can unscramble the permutation. This exercise
investigates how sensible that assumption is. Try to unscramble these
proposed lists of phrases into the correct order:<br />

1.  have, programming, a, seen, never, I, language, better<br />

2.  loves, john, mary<br />

3.  is the, communication, exchange of, intentional, information
    brought, by, about, the production, perception of, and signs, from,
    drawn, a, of, system, signs, conventional, shared<br />

4.  created, that, we hold these, to be, all men, truths, are, equal,
    self-evident<br />

Which ones could you do? What type of knowledge did you draw upon? Train
a bigram model from a training corpus, and use it to find the
highest-probability permutation of some sentences from a test corpus.
Report on the accuracy of this model.
</p>
</div>
</div>
<p><br /></p>
<div class="card">
<div class="card-header p-2">
<a href="ex_21/" class="p-2">Exercise 21 </a>
<button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch23ex21');" href="#"><i id="ch23ex21" class="fas fa-bookmark" style="color:white"></i></button>
<button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex23.21);" href="#"><i id="ch23ex21" class="fas fa-thumbs-up" style="color:white"></i></button>
</div>
<div class="card-body">
<p class="card-text">

Calculate the most probable path through the HMM in
Figure <a class="insideBookFigRef" target="_blank" href="https://aimacode.github.io/aima-exercises/figures/sr-hmm-figure.png">sr-hmm-figure</a> for the output sequence
$[C_1,C_2,C_3,C_4,C_4,C_6,C_7]$. Also give its probability.
</p>
</div>
</div>
<p><br /></p>
<div class="card">
<div class="card-header p-2">
<a href="ex_22/" class="p-2">Exercise 22 </a>
<button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch23ex22');" href="#"><i id="ch23ex22" class="fas fa-bookmark" style="color:white"></i></button>
<button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex23.22);" href="#"><i id="ch23ex22" class="fas fa-thumbs-up" style="color:white"></i></button>
</div>
<div class="card-body">
<p class="card-text">

We forgot to mention that the text in
Exercise <a class="exerciseRef" href="/aima-exercises/nlp-english-exercises/ex_1/">washing-clothes-exercise</a> is entitled “Washing
Clothes.” Reread the text and answer the questions in
Exercise <a class="exerciseRef" href="/aima-exercises/nlp-english-exercises/ex_17/">washing-clothes2-exercise</a>. Did you do better
this time? Bransford and Johnson [<a class="paperRef" title="" href="">Bransford+Johnson:1973</a>] used this
text in a controlled experiment and found that the title helped
significantly. What does this tell you about how language and memory
works?
</p>
</div>
</div>
<p><br /></p>

  </div>

<!--   <div class="date">
    Written on 
  </div>
 -->
  
</article>


      </div>
    <label for="sidebar-checkbox" class="sidebar-toggle"></label>
    <script>
      (function(document) {
        var toggle = document.querySelector('.sidebar-toggle');
        var sidebar = document.querySelector('#sidebar');
        var checkbox = document.querySelector('#sidebar-checkbox');
        document.addEventListener('click', function(e) {
          var target = e.target;
          if(!checkbox.checked ||
             sidebar.contains(target) ||
             (target === checkbox || target === toggle)) return;
          checkbox.checked = false;
        }, false);
      })(document);
    </script>
        <script src="/aima-exercises/js/main.js"></script>
        <script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.3/jquery.min.js"></script>
        <script src="/aima-exercises/js/answer.js"></script>
        <script src="/aima-exercises/js/commsol.js"></script>
        <script src="/aima-exercises/js/forms.js"></script>
        <script src="/aima-exercises/js/crossref.js"></script>
        <script src="/aima-exercises/js/bookmark.js"></script>
        <script src="https://cdn.jsdelivr.net/npm/marked/marked.min.js"></script>
  </body>
</html>
